template<const long long N>
struct StringHash {
    using i64 = long long;
    using PII = std::pair<i64, i64>;
    const i64 mod1 = 1e9 + 97, mod2 = 998244853, p1 = 131, p2 = 233;
    std::array<i64, N> a1, a2;
    std::array<i64, N> Phs1, Phs2;
    std::array<i64, N> Shs1, Shs2;
    StringHash() {
        init(N - 1);
    }
    StringHash(const std::string& S) {
        init(N - 1);
        work(S);
    }
    void work(const std::string& s) {  
        i64 n = s.size();
        assert(n + 1 <= N);
        for (int i = 0; i < n; ++i) {
            i64 t = n - i - 1;
            Phs1[i + 1] = ((i64)Phs1[i] * p1 + s[i]) % mod1;
            Phs2[i + 1] = ((i64)Phs2[i] * p2 + s[i]) % mod2;
            Shs1[t + 1] = ((i64)Shs1[t + 2] * p1 + s[t]) % mod1;
            Shs2[t + 1] = ((i64)Shs2[t + 2] * p2 + s[t]) % mod2;
        }
    }
    PII PreHash(i64 l, i64 r) {
        assert(l <= r);
        i64 P1 = (Phs1[r] - (i64)Phs1[l - 1] * a1[r - l + 1] % mod1 + mod1) % mod1;
        i64 P2 = (Phs2[r] - (i64)Phs2[l - 1] * a2[r - l + 1] % mod2 + mod2) % mod2;
        return PII(P1, P2);
    };
    PII SufHash(i64 l, i64 r) {
        assert(l <= r);
        i64 S1 = (Shs1[l] - (i64)Shs1[r + 1] * a1[r - l + 1] % mod1 + mod1) % mod1;
        i64 S2 = (Shs2[l] - (i64)Shs2[r + 1] * a2[r - l + 1] % mod2 + mod2) % mod2;
        return PII(S1, S2);
    }
    bool isPlalindrome(i64 l, i64 r) {
        auto [P1, P2] = PreHash(l, r);
        auto [S1, S2] = SufHash(l, r);
        return P1 == S1 && P2 == S2;
    }
    void init(i64 n) {
        a1[0] = a2[0] = 1;
        for (int i = 0; i < n; ++i) {
            a1[i + 1] = (i64)a1[i] * p1 % mod1;
            a2[i + 1] = (i64)a2[i] * p2 % mod2;
        }
    }
};
 
static const int N = 1e5 + 5;
StringHash<N> h;